package leetcode.median;

import java.util.*;

public class $03_LengthOfLongestSubstring {
    public int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        ArrayList<Integer> maxLengths = new ArrayList<>();
        char[] input = s.toCharArray();
        HashSet<Character> bag = new HashSet<>();
        for (int i = 0;i < input.length;i++){
            if (!bag.contains(input[i])){
                //无重复
                maxLength += 1;
                bag.add(input[i]);
                if (i == input.length - 1)
                    maxLengths.add(maxLength);
            } else {
                //出现重复
                maxLengths.add(maxLength);
                i = i - maxLength;
                maxLength = 0;
                bag.clear();
            }
        }

        if (maxLengths.size() == 0)
            return s.length();
        else
            return maxLengths.stream().max((v1, v2) -> {
                return v1 - v2;
            }).get();
    }

    public int lengthOfLongestSubstring2(String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0;
        int left = 0;
        for(int i = 0; i < s.length(); i ++){
            if(map.containsKey(s.charAt(i))){
                left = Math.max(left,map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-left+1);
            System.out.println("i: " + i + " left: " + left + " max: " + max);
            Set<Character> keys = map.keySet();
            for (Character key:keys) {
                System.out.println("key: " + key + " value: " + map.get(key));
            }
        }
        return max;

    }

    //aab
    public int lengthOfLongestSubstring3(String s) {
        int maxLength = 0;
        int max = 0;
        HashSet<Character> bag = new HashSet<>();
        for (int i = 0;i < s.length();i++){
            if (!bag.contains(s.charAt(i))){
                //无重复
                maxLength += 1;
                bag.add(s.charAt(i));
                if (i == s.length() - 1 && maxLength > max) {
                    max = maxLength;
                }
            } else {
                //出现重复
                if (maxLength > max) {
                    max = maxLength;
                }
                i = i - maxLength;
                maxLength = 0;
                bag.clear();
            }
        }

        return max;
    }

    public int lengthOfLongestSubstring4(String s) {
        if (s.length() == 0)
            return 0;
        int max = 0;
        int left = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0;i < s.length();i++) {
            char cur = s.charAt(i);
            if (map.containsKey(cur)) {
                left = Math.max(left, map.get(cur) + 1);
            }
            map.put(cur, i);
            max = Math.max(max, i - left + 1);
        }
        return max;
    }

    public int lengthOfLongestSubstring5(String s) {
        if (s.length() == 0) return 0;
        int max = 0;
        // 记录当前考虑的字符串区间的最左index
        int left = 0;
        // 记录某个字符上一次在第几个index出现
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0;i < s.length();i++) {
            char current = s.charAt(i);
            if (map.containsKey(current)) {
                // 如果当前字符之前出现过
                left = Math.max(map.get(current) + 1, left);
            }
            map.put(current, i);
            max = Math.max(max, i - left + 1);
        }

        return max;
    }

}
